#include <bits/stdc++.h>
#ifndef DEBUG
#define debug
#endif
using namespace std;
using i64 = int64_t;

const int mod = 998244353;
const i64 inf = LLONG_MIN / 2;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T --) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a) cin >> x;
    vector<vector<array<i64, 2>>> dp(n, vector<array<i64, 2>>(n, {inf, inf}));
    auto qpow = [&](i64 x, i64 y) -> i64 {
      if (x == 0 && y == 0) return 0;
      i64 res = 1;
      for (; y; y >>= 1, x = x * x % mod) {
        if (y & 1) res = res * x % mod;
      }
      return res;
    };
    for (int l = n - 1; l >= 0; l --) {
      dp[l][l][0] = dp[l][l][1] = 0;
      for (int r = l + 1; r < n; r ++) {
        dp[l][r][0] = max(
          dp[l + 1][r][0] + qpow(a[l], a[l + 1]),
          dp[l + 1][r][1] + qpow(a[l], a[r])
        );
        dp[l][r][1] = max(
          dp[l][r - 1][0] + qpow(a[r], a[l]),
          dp[l][r - 1][1] + qpow(a[r], a[r - 1])
        );
      }
    }
    cout << max(dp[0][n - 1][0], dp[0][n - 1][1]) << endl;
  }
}